#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph)
    {
        DFS(graph, 0, graph.size());
        return _path;
    }

private:
    void DFS(const std::vector<std::vector<int>>& graph, int start, int n)
    {
        if (start == n - 1)
        {
            _p.push_back(start);
            _path.emplace_back(_p);
            _p.pop_back();
            return;
        }

        _p.push_back(start);

        for (int node : graph[start])
        {
            DFS(graph, node, n);
        }

        _p.pop_back();
    }

    std::vector<int> _p;
    std::vector<std::vector<int>> _path;
};